public class Code03_WidthOfBinaryTree {
    // 二叉树的最大特殊宽度
    // 测试链接 : https://leetcode.cn/problems/maximum-width-of-binary-tree/
    // 不提交这个类
    public static class TreeNode {
        // 节点的值
        public int val;
        // 节点的左子节点
        public TreeNode left;
        // 节点的右子节点
        public TreeNode right;
    }

    // 提交以下的方法
    // 用每次处理一层的优化bfs就非常容易实现
    // 如果测试数据量变大了就修改这个值
    public static int MAXN = 3001;

    // 用于存储二叉树节点的队列
    public static TreeNode[] nq = new TreeNode[MAXN];
    // 用于存储对应节点编号的队列
    public static int[] iq = new int[MAXN];
    // 队列的头指针
    public static int l;
    // 队列的尾指针
    public static int r;

    public static int widthOfBinaryTree(TreeNode root) {
        // 用于存储二叉树的最大特殊宽度，初始化为1
        // 因为二叉树至少有一个节点，最小宽度为1
        int ans = 1;
        // 初始化队列的头指针和尾指针
        l = r = 0;
        // 将根节点加入节点队列nq
        nq[r] = root;
        // 将根节点的编号设为1（二叉树根节点编号为1）
        // 并将尾指针r后移一位
        iq[r++] = 1;

        // 只要队列里还有节点，就继续循环
        while (l < r) {
            // 确定当前层的节点数量
            int size = r - l;
            // 计算当前层的宽度并更新最大宽度ans
            // 宽度定义为当前层最右节点编号减去最左节点编号再加1
            ans = Math.max(ans, iq[r - 1] - iq[l] + 1);
            // 处理当前层的每个节点及其子节点
            for (int i = 0; i < size; i++) {
                // 获取当前层的节点
                TreeNode node = nq[l];
                // 获取当前节点的编号
                int id = iq[l++];
                // 如果节点的左子节点不为空
                if (node.left!= null) {
                    // 将左子节点加入节点队列nq
                    nq[r] = node.left;
                    // 根据二叉树节点编号规则（左子节点编号为父节点编号 * 2）
                    // 计算左子节点的编号并将其加入编号队列iq
                    // 然后将尾指针r后移一位
                    iq[r++] = id * 2;
                }
                // 如果节点的右子节点不为空
                if (node.right!= null) {
                    // 将右子节点加入节点队列nq
                    nq[r] = node.right;
                    // 根据二叉树节点编号规则（右子节点编号为父节点编号 * 2 + 1）
                    // 计算右子节点的编号并将其加入编号队列iq
                    // 然后将尾指针r后移一位
                    iq[r++] = id * 2 + 1;
                }
            }
        }
        // 返回二叉树的最大特殊宽度
        return ans;
    }
}